package String;

/**
 * 459.重复的子字符串
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 */
public class repeatedSubstringPattern {
    public boolean repeatedSubstringPattern(String s) {

        int j = 0;

        int[] next = new int[s.length()];
        next[0]=0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = next[j - 1];
            }
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
            next[i] = j;
        }
        if(next[s.length()-1]==0){
            return false;
        }
        return s.length()%(s.length()-next[s.length() - 1])==0?true:false;
    }
}
